#include<stdio.h>
#include<stdlib.h>

typedef char data_type;
typedef struct node
{
    data_type data;
    struct node *left;
    struct node *right;
    
}Treenode,*BinaryTree;

//先序遍历思路创建一个二叉树
data_type str[20]={"ABC**DE*G**F***"};
         /*
                  A
             B
         C      D  
            E      F
              G 
         */

//创建二叉树 用先序遍历思路创建一个二叉树
BinaryTree create_tree();
//先序遍历：根左右
void preorder_Traversal(BinaryTree root);
//中序遍历:左根右
void inorder_Traversal(BinaryTree root);
//后序遍历:左右根
void postorder_Traversal(BinaryTree root);
//销毁二叉树
void DestroyTree(BinaryTree *root);
//删除一个树节点
void DeleteTreeNode(Treenode *root, char data);

int main(int argc, char const *argv[])
{
    //创建一颗二叉树
    BinaryTree tree=create_tree();
    //先序
    printf("先序遍历\n");
    preorder_Traversal(tree);
    printf("\n");
    //中序
    printf("中序遍历\n");
    inorder_Traversal(tree);
    printf("\n");
    //后序
    printf("后序遍历\n");
    postorder_Traversal(tree);
    printf("\n");
    //删除一个结点
    printf("删除D所在的结点\n");
    DeleteTreeNode(tree,'B');
    printf("先序遍历\n");
    preorder_Traversal(tree);
    printf("\n");
    //销毁
    printf("销毁测试\n");
    DestroyTree(&tree);
    printf("先序遍历\n");
    preorder_Traversal(tree);
    printf("\n");
    return 0;
}

//创建二叉树 用先序遍历思路创建一个二叉树
BinaryTree create_tree()
{
    static int i=0;
    if(str[i]=='*')
    {
        i++;
        return NULL;
    }
    BinaryTree root=(BinaryTree)malloc(sizeof(Treenode));
    if(root==NULL)
    {
        printf("malloc failed\n");
        return NULL;
    }
    //将值赋给当前结点
    root->data=str[i];
    i++;
    //创建左孩子
    root->left=create_tree();
    //创建右孩子
    root->right=create_tree();
    return root;
}
//先序遍历：根左右
void preorder_Traversal(BinaryTree root)
{
    if(root==NULL)
    {
        return ;
    }
    printf("%c\t",root->data);
    preorder_Traversal(root->left);
    preorder_Traversal(root->right);
}
//中序遍历:左根右
void inorder_Traversal(BinaryTree root)
{
    if(root==NULL)
    {
        return ;
    }
    inorder_Traversal(root->left);
    printf("%c\t",root->data);
    inorder_Traversal(root->right);
}
//后序遍历:左右根
void postorder_Traversal(BinaryTree root)
{
    if(root==NULL)
    {
        return ;
    }
    postorder_Traversal(root->left);
    postorder_Traversal(root->right);
    printf("%c\t",root->data);
}
//销毁二叉树
void DestroyTree(BinaryTree *root)
{
    if((*root)==NULL)
    {
        return ;
    }
    //先销毁左孩子
    DestroyTree(&(*root)->left);
    //再销毁右孩子
    DestroyTree(&(*root)->right);
    //最后销毁根节点
    free(*root);
    *root=NULL;

    //当一个指针被释放后，它仍然保存着原来的地址，但该地址的内存已经不再属于程序
    //通过将指针置为NULL，可以避免这种悬空指针的问题
}
//删除一个树节点
void DeleteTreeNode(Treenode *root, char data)
{
    if(root==NULL)
    {
        return ;
    }
    if(root->data==data)
    {
        free(root);
        root=NULL;
        return ;
    }
    if(root->left!=NULL&&root->left->data==data)
    {
        free(root->left);
        root->left=NULL;
        return ;
    }
    if(root->right!=NULL&&root->right->data==data)
    {
        free(root->right);
        root->right=NULL;
        return ;
    }
    //递归删除左子树和右子树
    DeleteTreeNode(root->left,data);
    DeleteTreeNode(root->right,data);
}
